COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.if false then begin
C00007 00003	a277  1854  18 Nov 81
C00011 00004	.require "memo.pub[let,jmc]" source
C00013 00005	#. Derived functions
C00015 00006	#. Occurrences of an atom in an S-expression.
C00016 00007	#. Improving LCOM4
C00017 00008	# Pattern matching and substitution
C00019 00009	#. Simplifying expressions
C00020 ENDMK
C⊗;
.if false then begin
a059  0445  18 Nov 81
PM-Shuttle Buy,480
Private Investors Trying To Buy Space Shuttle
    PRINCETON, N.J. (AP) - A group of private investors has approached
the Reagan administration to propose buying a space shuttle in what
would mark the beginning of major private-sector involvement in the
nation's space program, one person involved in the venture says.
    Officials at the Space Transportation Co. of Princeton, N.J., want
to buy a shuttle similar to the Columbia and rent it out to an
operator - either the National Aeronautics and Space Administration or
a private entity, the Dallas Morning News reported today.
    ''Essentially, there are a lot of people paying a lot of money for
satellites to do what a shuttle can do cheaper,'' said William H.
Sword Jr., who with his father is part of a Princeton investment firm
organizing the planned venture.
    ''We think private business will be able to handle all that future
business more efficiently than the government,'' the younger Sword
told The Associated Press in a telephone interview from his home in
Cranbury, N.J. today.
    ''Personally, I have for a long, long time felt that private
commitment of funds for space is the key to the success of the U.S.
space program,'' the Dallas newspaper quoted Dr. Klaus Heiss as
saying. He is guiding the company's effort to purchase a shuttle.
    The firm recently presented its proposal to the administration's
science adviser, George Keyworth, who heads a federal study on
long-range space policy, the News said.
    ''We think now, particularly in the current budget environment, that
private financing is a key symbol, and in fact, more than a symbol,
of space policy in the 1980s,'' said Heiss, who directed economic
studies from 1969 to 1971 leading to 5he original shuttle program.
    The shuttle purchase ''is feasible and we want to seriously, quietly
and diligently pursue whether ... the administration and the
aerospace community and the financial community can be persuaded that
indeed that is a viable option,'' he added.
    Government officials would not comment on the proposal, other than
to say discussions did take place between the company and members of
the government's office of science and techonology policy.
    ''It is a somewhat revolutionary idea,'' Heiss said. ''There are
many skeptics within the government and the aerospace community.''
    The Columbia, which completed a second mission Saturday, and four
other orbiters originally were planned by NASA. The Columbia is the
only finished orbiter, but NASA has contracts for three more, the last
scheduled for delivery in September 1984.
    The Space Transportation Co. wants to buy the fifth shuttle, the
newspaper said.
    A consultant with the Space Transportation Co. said the firm has a
minimum of $200 million in an escrow account, but Heiss would not
confirm or deny that. The Columbia cost more than $500 million.
    ''There's no doubt they can raise every nickel required,'' said
Gilbert Keyes, an official with Boeing Aerospace Co., who is familiar
with the firm's effort.
    
ap-ny-11-18 0746EST
***************

a277  1854  18 Nov 81
AM-Shuttle Buy,340
Private Investors Trying To Buy Space Shuttle
    PRINCETON, N.J. (AP) - A group of private investors that contends
space shuttles can be profitable has offered to buy one similar to the
Columbia, which made its second round trip last week.
    The group, Space Transportation Co., negotiated with the federal
government last Friday and said it would pay for a fifth shuttle in
return for an exclusive agreement to market all non-government
activity on the craft, company president William Sword said Wednesday.
    ''This is not a joke,'' Sword said. ''It's not Star Wars and it's
not Space Invaders. We're serious as the devil.''
    Sword said the investment group received a ''favorable reception''
but admitted final agreement to the proposal would be a long way off.
    He said the group negotiated with ''contacts in the executive
branch,'' but would not identify who they were.
    The Dallas Morning News said the firm spoke with President Reagan's
science adviser, George Keyworth, who heads a federal study on
long-range space policy.
    Under the proposal, STC would fund the fifth shuttle and rent it out
to an operator - either the National Aeronautics and Space
Administration or a private entity, the Morning News said.
    ''Essentially, there are a lot of people paying a lot of money for
satellites to do what a shuttle can do cheaper,'' said Sword's son,
William H. Sword Jr., in a telephone interview from his home in
Cranbury, N.J.
    Government officials would not comment on the proposal, other than
to say discussions did take place between the company and members of
the government's Office of Science and Techonology Policy.
    The Columbia and four other orbiters originally were planned by
NASA. The Columbia is the only finished orbiter, but NASA has
contracts for three more, the last scheduled for delivery in September
1984.
    A consultant with the Space Transportation Co. said the firm has a
minimum of $200 million in an escrow account, but Sword would not
confirm or deny that. The Columbia cost more than $500 million.
    
ap-ny-11-18 2151EST
***************
.end
.require "memo.pub[let,jmc]" source
.turn on "→"
CS206∂(30)FINAL EXAMINATION→FALL 1981
.turn off "→"

	This examination is open book and notes.
Write LISP functions or predicates and make proofs
 as follows except where something else is
requested.  Either notation may be used.
Be sure to indicate in an emphatic way the logical sentences indicating
what is to be proved and the %AF%*'s of any inductions that need to be
made.  You may assume that your functions are total but will be
suitably penalized if they aren't.

	The examination is a "take home" and is due at 1981 December 17
Thursday 7pm in Room 353 Margaret Jacks Hall.  It may also be left
earlier with Mrs. Larson in Room 358 Margaret Jacks Hall.
.item←0

#. Derived functions

	Certain properties of LISP functions are expressed by related
functions called derived functions.  For example, consider

%2flatten x ← qif qat x qthen <x> qelse flatten qa x * flatten qd x%1.

Let %2cflatten x%1 be the number of times LISP executes ⊗cons in
evaluating %2flatten x%1.  Clearly ⊗cflatten satisfies the recursions

%2cflatten x ← qif qat x qthen 1
	qelse cflatten qa x + cflatten qd x + cappend[flatten qa x, flatten qd x]%1,

where ⊗cappend[u,v] is the number of conses done in computing %2u*v%1
and satisfies

%2cappend[u,v] ← qif qn u then 0 qelse 1 + cappend[qd u, v]%1.

	Our other way of flattening a list involves

%2flat[x,u] ← qif qat x qthen x.u qelse flat[qa x, flat[qd x, u]]%1.

Let ⊗cflat[x,u] be the number of %2cons%1es done in computing %2flat[x,u]%1.

	a. Write the recursion for %2cflat[x,u]%1.

	b. Prove %2cflat[x,u] ≤ cflatten x%1.

#. Occurrences of an atom in an S-expression.

	Define

%2occurs[x,y] ← qif qat y qthen x = y qelse occurs[x, qa y] ∨ occurs[x, qd y]%1.

and

%2occurrences[x,y,u] ← qif qat y qthen [qif x = y qthen x.u qelse u] qelse occurrences[x, qa y, occurrences[x,qd y, u]]%1.

%1Prove

	%2∀x.atom x ⊃ ∀y.occurs[x,y] ≡ member[x, occurrences[x,y,qnil]]%1.

#. Improving LCOM4

	Page 172 of the text gives code compiled by LCOM4 for the function
%2drop%1 defined slightly earlier in the text.

a. Why is the second executed instruction (MOVE 1 0 P) unnecessary?

b. Describe modifications to LCOM4 that would (preserving correctness)
avoid generating this instruction.

# Pattern matching and substitution

	%2sublis[pattern, alist]%1 is the result of making the
substitutions described in ⊗alist in ⊗pattern.  Thus

%2sublis%1[(PLUS X (TIMES X Y) A), ((X.A) (Y.(PLUS X Y)))] = (PLUS A (TIMES X (PLUS X Y)))

%2match[pattern,expression,alist]%1 attempts to match ⊗pattern against
⊗expression to produce and extension of ⊗alist such that substituting
in the pattern according to the result will lead give back %2expression%1.
If the match is unsuccessful, the value is the atom NO.  It is assumed
that a predicate  ⊗isvar  applicable to atoms is available that distinguish
es variables from other atoms.  Assuming that ⊗X and ⊗Y are variables, we have

%2match%1[(PLUS X Y), (PLUS A (TIMES B C)),qnil] = ((X.A) (Y TIMES B C)),

and

%2match%1[(PLUS X Y), (PLUS A (TIMES B C)),((X.B))] = NO.

a. Write recursive programs for ⊗sublis and ⊗match. 

b. Write accurately the sentence that expresses the fact that
⊗sublis and ⊗match are partial inverses.

c. Prove the sentence of part b.
#. Simplifying expressions

	Write a program for simplifying expressions formed from
sums and products that 

(1) appropriately eliminates sums and products with zero or one terms.

(2) drops summands that are 0 and factors that are 1

(3) drops products that have a term that is 0

b. Prove that for all values of the variables, the
simplified expression has the same value as the original expression.

c. Define an appropriate complexity and prove that the result of
simplification is not more complex than the input.